package test;

public class ClimbStairs {

	public static void main(String[] args) {
		System.out.println(calculateCount(20,3) + "...." + calculateCount(20));
	}
	/**
	 * 假设一个楼梯有 N 阶台阶，人每次最多可以跨 M 阶，求总共的爬楼梯方案数。
	 * 例如楼梯总共有3个台阶，人每次最多跨2个台阶，也就是说人每次可以走1个，也可以走2个，但最多不会超过2个，
	 * 那么楼梯总共有这么几种走法?
	 * @param ladder 楼梯数
	 * @param maxJump 最大跨越数
	 * */
	@SuppressWarnings("unused")
	private static int calculateCount(int ladder, int maxJump) {
		int jump = 0;
		if (ladder == 0) {
			return 1;
		}
		// 剩下的楼梯大于最大可跳跃数
		if (ladder >= maxJump) {
			for (int i = 1; i <= maxJump; i++) {
				jump += calculateCount(ladder - i, maxJump);
			}
		}else {
			// 剩下的楼梯不足最大可跳跃数
			jump = calculateCount(ladder, ladder);
		}
		return jump;
	}
	
	/**
	 * 假设一个楼梯有 N 阶台阶，人每次最多可以跨 2 阶，求总共的爬楼梯方案数
	 * @param ladder 台阶数量
	 * @return 总的爬法
	 * */
	@SuppressWarnings("unused")
	private static int calculateCount(int ladder) {
	    if (ladder == 1 || ladder == 2) {
	        return ladder;
	    }
	    int n1 = 1;
	    int n2 = 2;
	    for (int i = 3; i <= ladder; i++) {
	        int tmp = n2;
	        n2 = n1 + n2;
	        n1 = tmp;
	    }
	    return n2;
	}
}
